Finding the minimum connected dominating set (MCDS) is a key problem in wireless sensor networks, which is\ncrucial for efficient routing and broadcasting. However, the MCDS problem is NP-hard. In this paper, a new\napproximation algorithm with approximation ratio H() + 3 in time O\n\nn2\nis proposed to approach the MCDS\nproblem. The key idea is to divide the sensors in CDS into core sensors and supporting sensors. The core sensors\ndominate the supporting sensors in CDS, while the supporting sensors dominate other sensors that are not in CDS. To\nminimize the number of both the cores and the supporters, a three-phased algorithm is proposed. (1) Finding the\nbase-core sensors by constructing independent set (denoted as S1), in which the sensors who have the largest |N2(v)|\n|N(v)|\n(number of two-hop neighbors over the number of one-hop neighbors) will be selected greedily into S1; (2)\nConnecting all base-core sensors in S1 to form a connected subgraph, the sensors in the subgraph are called cores; (3)\nAdding the one-hop neighbors of the core sensors to the supporter set S2. This guarantees a small number of sensors\ncan be added into CDS, which is a novel scheme for MCDS construction. Extensive simulation results are shown to\nvalidate the performance of our algorithm.
Loading....